'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-09-24 08:29:20
'''
'''
501. 二叉搜索树中的众数
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],

   1
    \
     2
    /
   2
返回[2].

提示：如果众数超过1个，不需考虑输出顺序

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

tips:简单递归，在过程中维护一些结果量。本题就需要维护一个ans列表还有一个use列表，use中存储0.ans中数字出现的次数
1.目前遍历到的数字出现的次数 2.目前遍历的数字。
啊对，既然是搜索树，那么中序遍历就是顺序输出。注意两点，global的量或者传入的list量，不能重新复制，否则变量地址变了，
传不到函数外，只能clear再append。最后再做一次判断，不然最后的值不能计算在内了。
'''

from tree_node import *
from typing import List
class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        use=[1, 0, -1] #0 for the current time of ans, 1 for the times of 2
        ans = []
        def recurse(root):
            if not root:
                return
            recurse(root.left)
            if root.val == use[2]:
                use[1]+=1
            else:
                if use[1]==use[0]:
                    ans.append(use[2])
                if use[1] > use[0]:
                    ans.clear()
                    ans.append(use[2])
                    use[0]=use[1]
                use[1]=1
                use[2]=root.val
            recurse(root.right)
        recurse(root)
        if use[1]==use[0]:
            ans.append(use[2])
        if use[1] > use[0]:
            ans.clear()
            ans.append(use[2])
        # print(use)
        return ans
if __name__ == "__main__":
    solution = Solution()
    null = 'null'
    root = [1,null,2,2]
    for i,v in enumerate(root):
        root[i] = str(v)
    s = ','.join(root)
    # print(s)
    o_s = OfficialSerialize()
    root = o_s.deserialize(s)
    print(solution.findMode(root))